package snippets.cse524.activeDates;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.Reader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.apache.commons.collections.CollectionUtils;
import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;

import snippets.cse524.activeDates.Link.LinkComparator;
import snippets.utils.Utils;

public class ReconstructChain {
	
	private static final Link link = new Link("dummy");
	private static final LinkComparator linkComparator = link.new LinkComparator();

	private static final int CHAIN_LENGTH = 3;

	private static Map<String, String> canonicalNames = new HashMap<String, String>();

	public static void main(String args[]) throws FileNotFoundException {

		Reader in = null;

		if (args.length > 0) {
			in = new FileReader(new File(args[0]));
		} else {
			in = new StringReader("o\te\tf\tg\no\ta\tb\tc\no\tc\td\te\n");
		}

		if (args.length > 1) {
			System.err.print("Reading canonical names ... ");
			readCanonicalNames(new File(args[1]));
			System.err.println("done.");
		}

		if (args.length > 2) {
			Scanner _in = new Scanner(in);
			while (_in.hasNextLine()) {
				String line = _in.nextLine().trim();

				String[] parts = StringUtils.split(line, '\t');

				for (int i = 1; i < parts.length; ++i) {
					String part = parts[i].toLowerCase();
					// check if there's a canonical name for this guy

					part = part.replace("acting", "").trim();

					parts[i] = canonicalNames.containsKey(part.toLowerCase()) ? canonicalNames
							.get(part.toLowerCase()) : part;
				}

				System.out.println(StringUtils.join(parts, '\t'));
			}

			return;
		}

		Map<String, Map<Link, List<String>>> officeChains = readOfficeChains(in);

		printChains(officeChains);
	}

	private static void readCanonicalNames(File input)
			throws FileNotFoundException {
		Scanner in = new Scanner(input);

		while (in.hasNextLine()) {
			String line = in.nextLine().trim();

			String[] parts = StringUtils.split(line);

			if (parts.length != 3) {
				System.err.println("Invalid canonical name line : "
						+ StringUtils.join(parts, " ## "));
				continue;
			}

			String left = StringUtils.join(StringUtils.split(parts[0], '_'),
					' ').toLowerCase();

			canonicalNames.put(left, parts[1]);
		}
	}

	private static void printChains(
			Map<String, Map<Link, List<String>>> officeChains) {
		for (String office : officeChains.keySet()) {
			// System.err.println("Looking for " + office);
			Map<Link, List<String>> chains = officeChains.get(office);

			compress(chains);
			printAChain(office, chains);
		}
	}

	private static void printAChain(String office,
			Map<Link, List<String>> chains) {
		List<Link> keys = new ArrayList<Link>(chains.keySet());
		
//		List<List<String>> allChains = new ArrayList<List<String>>(chains.values());
		
		Collections.sort(keys, linkComparator);
		
		List<List<String>> allChains = new ArrayList<List<String>>();
		
		for (Link begin : keys) {
			allChains.add(chains.get(begin));
		}

		if(allChains.size() == 0) {
			return;
		}
		
		while(allChains.size() > 1) {
//			Collections.sort(allChains, new Comparator<List<String>>() {
//				@Override
//				public int compare(List<String> o1, List<String> o2) {
//					// For descending order sort
//					return o2.size() - o1.size();
//				}
//			});
			
			List<String> left = allChains.get(0);
			List<String> right = allChains.get(1);
			
			if(left.contains("nobody")) {
				left.remove("nobody");
			}
			if(right.contains("nobody")) {
				right.remove("nobody");
			}
			
			allChains.remove(0);
			allChains.remove(0);
			
			left.addAll(right);
			allChains.add(left);
			
//			allChains.add(0, approxOverlap(left, right));
		}

		System.out.println(office.toUpperCase());
		System.out.println(StringUtils.join(allChains.get(0), ",\t"));
		System.out.println();
		
		return;
	}

	private static Map<String, Map<Link, List<String>>> readOfficeChains(
			Reader input) {
		Scanner in = new Scanner(input);
		Map<String, Map<Link, List<String>>> officeChains = new HashMap<String, Map<Link, List<String>>>();

		while (in.hasNextLine()) {
			String line = in.nextLine();

			String[] parts = StringUtils.split(line, '\t');
			for (int i = 1; i < parts.length; ++i) {
				String part = parts[i].toLowerCase();
				// check if there's a canonical name for this guy

				part = part.replace("acting", "").replaceAll("\\.", "").trim();

				parts[i] = canonicalNames.containsKey(part.toLowerCase()) ? canonicalNames
						.get(part.toLowerCase()) : part;
			}

			if (parts.length != CHAIN_LENGTH + 2) {
				// System.err.println("Invalid line: " + line + " of length "
				// + parts.length + ", ignoring.");
				continue;
			}

			Pattern year = Pattern.compile("([0-9]{4})");
			Matcher yearMatcher = year.matcher(parts[1]);

			int minYear = Integer.MAX_VALUE;
			int maxYear = Integer.MIN_VALUE;

			while (yearMatcher.find()) {
				int thisYear = Integer.parseInt(yearMatcher.group());

				if (thisYear < minYear)
					minYear = thisYear;
				if (thisYear > maxYear)
					maxYear = thisYear;
			}

			if (minYear == Integer.MAX_VALUE)
				minYear = -1;
			if (maxYear == Integer.MIN_VALUE)
				maxYear = -1;

			if (!officeChains.containsKey(parts[0])) {
				officeChains.put(parts[0], new HashMap<Link, List<String>>());
			}

			Link key = new Link(parts[2], minYear, maxYear);

			List<String> list = new ArrayList<String>(Arrays.asList(ArrayUtils
					.subarray(parts, 2, parts.length)));

			officeChains.get(parts[0]).put(key, list);
		}


		return officeChains;
	}

	private static void compress(Map<Link, List<String>> chains) {
		int parts = chains.size();
		int lastParts = parts + 1;

		while (lastParts != parts) {
			Set<Link> keys = new HashSet<Link>(chains.keySet());

			for (Link begin : keys) {
				// System.err.println("Looking for key: " + _begin);
				if (begin == null)
					continue;

				if (chains.get(begin) == null) {
					lastParts = parts;
					parts = chains.size();
					chains.remove(begin);

					continue;
				}

				if (chains.get(begin).size() < 1) {
					// WTF?
					continue;
				}

				// String lastStr = chains.get(begin).get(
				// chains.get(begin).size() - 1);

				Link last = null;
				int overlapLength = 0;

				for (Link _candidate : chains.keySet()) {
					if (chains.get(_candidate) == null || _candidate == begin)
						continue;

					if ((overlapLength = overlap(chains.get(begin),
							chains.get(_candidate))) > 0
							&& linkComparator.compare(_candidate, begin) >= 0) {
						last = _candidate;
						break;
					}
				}

				if (last != null && chains.get(last) != null
						&& overlapLength > 0 && last != begin) {

//					System.err.println("MERGING "
//							+ StringUtils.join(chains.get(begin), ", ")
//							+ " WITH "
//							+ StringUtils.join(chains.get(last), ", "));

					List<String> trailing = chains.get(last);

					if (overlapLength < trailing.size()) {
//						System.err.println("Partial overlap.");
						trailing = trailing.subList(overlapLength,
								trailing.size());

						Link newLink = new Link(begin.title, begin.beginYear,
								last.endYear);
						List<String> result = new ArrayList<String>();
						result.addAll(chains.get(begin));
						result.addAll(trailing);

						chains.remove(begin);
						chains.put(newLink, result);
					} else {
						// System.err.println("Full overlap.");
					}

					chains.remove(last);
					break;
				}
			}

			lastParts = parts;
			parts = chains.size();
		}
	}

	public static int overlap(List<String> left, List<String> right) {
		// System.err.println("CHECKING " + StringUtils.join(left, ", ") +
		// " and " + StringUtils.join(right, ", "));

		for (int loc = 0; loc < left.size(); ++loc) {
			List<String> leftPart = left.subList(loc,
					Math.min(loc + right.size(), left.size()));
			List<String> rightPart = right.subList(0,
					Math.min(right.size(), left.size() - loc));

			// System.err.println("CHECKING PART " + StringUtils.join(leftPart,
			// ", ") + " and " + StringUtils.join(rightPart, ", "));

			assert (leftPart.size() == rightPart.size());

			boolean match = true;
			for (int i = 0; i < leftPart.size(); ++i) {
				if (!leftPart.equals(rightPart)) {
					match = false;
					break;
				}
			}

			if (match) {
				// System.err.println("Overlap between " +
				// StringUtils.join(left, ", ") + " and " +
				// StringUtils.join(right, ", ") + " : " + (left.size() - loc));
				return left.size() - loc;
			}
		}

		// System.err.println("No overlap between " + StringUtils.join(left,
		// ", ") + " and " + StringUtils.join(right, ", "));
		return -1;
	}
	
	
	public static List<String> approxOverlap(List<String> left, List<String> right) {
		// System.err.println("CHECKING " + StringUtils.join(left, ", ") +
		// " and " + StringUtils.join(right, ", "));

		int maxOverlapCount = 0;
		int maxOverlapLoc = -1;
		
		for (int loc = 0; loc < left.size(); ++loc) {
			List<String> leftPart = left.subList(loc,
					Math.min(loc + right.size(), left.size()));
			List<String> rightPart = right.subList(0,
					Math.min(right.size(), left.size() - loc));

			// System.err.println("CHECKING PART " + StringUtils.join(leftPart,
			// ", ") + " and " + StringUtils.join(rightPart, ", "));

			assert (leftPart.size() == rightPart.size());

			int overlapCount = 0;
			for (int i = 0; i < leftPart.size(); ++i) {
				if (!leftPart.equals(rightPart)) {
					overlapCount += 1;
					break;
				}
			}

			if (overlapCount > maxOverlapCount) {
				maxOverlapCount = overlapCount;
				maxOverlapLoc = loc; 
			}
		}

		List<String> result = new ArrayList<String>(right);

		if(maxOverlapCount != 0) {
			result.addAll(maxOverlapLoc + maxOverlapCount, left.subList(maxOverlapCount, left.size()));
		} else {
			result.addAll(left);
		}
		
		// System.err.println("No overlap between " + StringUtils.join(left,
		// ", ") + " and " + StringUtils.join(right, ", "));
		return result;
	}

	private static String[] NON_NAME_WORDS = new String[] { "acting" };

	public static int compare(String o1, String o2) {
		int orig = o1.compareTo(o2);

		if (orig == 0)
			return 0;

		Set<String> o1Parts = new HashSet<String>();
		Set<String> o2Parts = new HashSet<String>();

		for (String part : StringUtils.split(o1)) {
			o1Parts.add(part.toLowerCase());
		}

		for (String part : StringUtils.split(o2)) {
			o2Parts.add(part.toLowerCase());
		}

		if (o1Parts.size() == o2Parts.size())
			return orig;

		for (String nonNameString : NON_NAME_WORDS) {
			o1Parts.remove(nonNameString);
			o2Parts.remove(nonNameString);
		}

		Set<String> intersection = new HashSet<String>(o1Parts);
		intersection.retainAll(o2Parts);

		if (intersection.size() == Math.min(o1Parts.size(), o2Parts.size())) {
			return 0;
		}

		return orig;
	}
}
